COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	                          WORD BIT REVERSAL
C00004 00003	The Gosper triple tricky is merely the observation that
C00006 00004	BYTE SERIAL SCHEMES
C00007 00005	TITLE	D1
C00008 ENDMK
C⊗;
                          WORD BIT REVERSAL

                              Baumgart



ABSTRACT:	Thirty or so PDP-10 programs for reversing the  order
of  the  bits  in  a  word are presented and anaylsed; although these
programs were written for their peculiar  entertainment  value,  they
are  subsequently discussed with respect to proving their correctness
and equivalence and with respect to generating
arbitrary repacking programs automatically.

	A series	-	Simple Serial.
	B series	-	Gosper Triple Tricky.
	C series	-	Byte Serial.
	D series	-	Nested Byte Swapping.
	E series	-	Schroeppel Bit-Rev'ing.
	F series	-	Combination Schee

TITLE	A1
INTERN	REV			; 183 memory cycles.
	A←←1			;   8 words long.
	B←←2
	CNT←←3
	P←←17
REV:	MOVEI	CNT,=36		;1
L:	LSHC	1		;36
	EXCH	A,B		;36
	LSHC	-1		;36
	EXCH	A,B		;36
	SOJG	CNT,L		;36
	MOVE	A,B		;1
	POPJ	P,		;1
END

TITLE	A2
INTERN	REV				; 57 memory cycles.
	A←←1				;  7 words.
	B←←2
	PTR←←3
	P←←17
REV:	MOVE	PTR,[POINT 1,B,-1]	;1
L:	IDPB	A,PTR			;18 average
	LSH	A,-1			;18 average
	JUMPN	A,L			;18 average
	MOVE	A,B
	POPJ	P,
END
The Gosper triple tricky is merely the observation that
	TRCE	PAIR
	TRCE	PAIR
	TRCE	PAIR
will swap two bits in the right half of the ac; where PAIR is a 
suitable mask indicating the two bit position you wish to swap.
One might hope that this code fragment could be the basis of
a good REV program.

TITLE	B1	TRIPLE TRICKY with COMPUTED MASK.
INTERN	REV			; 156 memory cycles.
	A←←1			;  12 words long.
	P←←17
	LBIT←2
	RBIT←3
	MASK←4
REV:	MOVEI	RBIT,1		; 1
	HRLZI	LBIT,400000	; 1
L:	MOVE	MASK,LBIT	;18
	IOR	MASK,RBIT	;18
	TDCE	A,MASK		;18
	TDCE	A,MASK		;13.5
	TDCE	A,MASK		;13.5
	LSH	LBIT,-1		;18
	CAMN	LBIT,RBIT	;18
	POPJ	P,		; 1
	LSH	RBIT,1		;18
	JRST	L		;18
END

TITLE	B2	TRIPLE TRICKY with TABLE MASK.
INTERN	REV				;101 memory cycles.
	A←←1				; 25 words long.
	CNT←←2
	MASK←←3
REV:	MOVEI	CNT,=18			; 1
L:	MOVE	MASK,TABLE(CNT)		;18
	TDCE	A,MASK			;18
	TDCE	A,MASK			;13.5
	TDCE	A,MASK			;13.5
	SOJG	CNT,L			;18
	POPJ	P,			; 1
TABLE:	FOR I←0,=17{
	((1B0)⊗(-I))∨(1⊗I)}
END
BYTE SERIAL SCHEMES

TITLE	C1	NAIVE STRAIGHT TABLE LOOKUP IN THREE 12-BIT BYTES.
INTERN	REV
	A←←1
	B←←2
	X←←3
	P←←17
REV:	LDB	X,[POINT 12,A,11]
	MOVE	X,TABLE(X)
	DPB	X,[POINT 12,A,35]
	LDB	X,[POINT 12,A,23]
	MOVE	X,TABLE(X)
	DPB	X,[POINT 12,B,23]
	LDB	X,[POINT 12,A,35]
	MOVE	X,TABLE(X)
	DPB	X,[POINT 12,B,11]
	MOVE	A,B
	POPJ	P,
END


TITLE C2
INTERN REV				;34 memory cycles.
	A←←1				;72 words long.
	AA←←2
	BB←←3
	CNT←←4
	PTR←←5
	P←←17
REV:	MOVE	PTR,[POINT 6,A,-1]	;1
	MOVEI	CNT,6			;1
L:	ILDB	AA,PTR			;6
	MOVE	AA,TABLE(AA)		;6
	LSHC	AA,-6			;6
	SOJG	CNT,L			;6
	MOVE	A,BB			;1
	POPJ	P,			;1
END
TITLE	D1
INTERN REV				;27 memory cycles.
	A←←1				;25 words long.
	B←←2
	C←←3
REV:	MOVS	A
	ROTC	9
	HRL	A,
	MOVE	C,A
	AND	C,[007007007007]
	LSH	C,6
	MOVE	B,A
	AND	B,[070070070070]
	IOR	C,B
	LSH	A,-6
	AND	A,[007007007007]
	IORB	A,C
	AND	C,[111111111111]
	LSH	C,2
	MOVE	B,A
	AND	B,[222222222222]
	IOR 	C,B
	LSH	A,-2
	AND	A,[111111111111]
	IOR	A,C
	POPJ	P,
END